package newBee.class4;

import java.util.PriorityQueue;

/**
 * https://leetcode.cn/problems/minimum-cost-to-cut-a-stick/
 * 切棍子的最小成本 - 贪心算法下
 */
public class Code04_minCost {
    public static void main(String[] args) {
        int[] cuts = {3, 5, 1, 4};
        int k = 7;
        int i = minCost(k, cuts);
        System.out.println("i = " + i);
    }

    public static int minCost(int n, int[] cuts) {
        PriorityQueue<Integer> pQ = new PriorityQueue<>();
        for (int i = 0; i < cuts.length; i++) {
            pQ.add(cuts[i]);
        }
        int sum = 0;
        while (pQ.size() > 1) {
            int cur = pQ.poll() + pQ.poll();
            sum+=cur;
            pQ.add(cur);
        }
        return sum;
    }
}
